/**
 * 朴素的模式匹配法
 * @param s 主串
 * @param t 子串
 * @returns {number}
 */
function findIndex(s: string, t: string): number {
  // 遍历主串
  for (let i = 0; i < s.length; i++) {
    // 遍历子串
    for (let j = 0; j< t.length; j++) {
      if ((i + j ) > s.length - 1) {
        return -1
      }
      if (s[i+j] != t[j]) {
        break
      } else {
        if (j == t.length - 1) {
          return i
        }
      }
      
    }

  }
  return -1

}

function getNext(t: string): Array<number> {
  let next: Array<number> = []
  // ababbacdefg

  let tLength = t.length
  let i = 1
  let j = 0
  next[i] = 0

  while ( i < tLength) {
    if (j==0 || t[i-1] == t[j-1]) {
      i++
      j++
      next[i] = j
    } else {
      j = next[j]
    }
  }
  return next
}

function kmp(s:string, t: string): number {
  let next = getNext(t)
  let i = 0
  let j = 0

  while (i <= s.length  && j <= t.length) {
    // console.log(i, j, s[i-1], t[j-1])
    if (j == 0 || s[i-1] == t[j - 1]) {
      i++
      j++
    } else {
      j = next[j]
    }
  }

  if (j > t.length) {
    return i - j
  }

  return -1
}

function main() {
  let s = "oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo"
  let l = 0
  while (l++ < 20) {
    s += s
  }
  s += "a"
  let t = "ooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooa"
  console.time('simple')
  let index = findIndex(s, t)
  console.timeEnd("simple")

  // console.log(getNext("ababacb"))
  console.time("kmp")
  let kmpIndex = kmp(s, t)
  console.timeEnd('kmp')

  console.log(index, kmpIndex)
}

main()